UVa/357 - Let me count the ways/p357.cpp

   1 #include <iostream>
   2
   3 using namespace std;
   4
   5 #define M 3
   6 int m[] = {1,2, 5};//, 10, 25, 50};
   7
   8 long long f(const int &n, const int &i){
   9   if (n < 0){
  10     printf("f(%d,%d) retornando 0\n", n, i);
  11     return 0;
  12   }
  13   if (n <= 1 || i == 1){
  14     printf("f(%d,%d) retornando 1\n", n, i);
  15     return 1;
  16   }
  17   long long r=0;
  18   for (int j=1; j<=M; ++j)
  19     r += f(n-m[j-1], j);
  20   printf("f(%d,%d) retornando %lld\n", n, i, r);
  21   return r;
  22 }
  23
  24 long long f(const int &n){
  25   //printf("n es: %d\n", n);
  26   if (n < 0) return 0;
  27   if (n <= 1) return 1;
  28
  29
  30   int pisoMonetario = 9999;
  31   for (int i=M-1; n < pisoMonetario; --i)
  32     pisoMonetario = m[i];
  33   //pisoMonetario tiene la moneda más proxima hacia abajo
  34
  35   //printf("pisoMonetario es: %d\n", pisoMonetario);
  36
  37  long long r=0;
  38   for (int i=0; i<M; ++i){
  39     //printf("i es: %d\n", i);
  40     //printf("m[i] es: %d\n", m[i]);
  41     if (n - m[i] > pisoMonetario)
  42       r += f(n - m[i]);
  43   }
  44   return r;
  45
  46 }
  47
  48 int main(){
  49   int n;
  50   while (scanf("%d", &n) == 1){
  51     cout << f(n, M) << endl;
  52   }
  53   return 0;
  54 }